from collections import defaultdict
def min_window(s,t):
    need = defaultdict(int)
    window = defaultdict(int)
    valid = 0
    left,right,start = 0,0,0
    sub_len = float('inf')
    for i in t:
        need[i]+=1

    while right < len(s):
        c = s[right]
        right +=1
        if c in need:
            window[c]+=1
            if window[c]==need[c]:
                valid+=1

        while valid ==len(need):
            if right -left < sub_len:
                sub_len = right -left
                start = left
            d = s[left]
            left +=1
            if d in need:
                if need[d]==window[d]:
                    valid -=1
                    window[d]-=1

    return s[start:start+sub_len]

if __name__=="__main__":
    S="ADOBECODEBANC"
    T = "ABC"
    r =min_window(S,T)
    print(r)
